package com.zhang;

import com.zhang.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树实现
 *
 * @param <E> 泛型E
 */
public class BinarySearchTree2<E> implements BTree<E>, BinaryTreeInfo {
    /**
     * 数量
     */
    private int size;

    /**
     * 根节点
     */
    private Node<E> root;

    /**
     * 比较器，暴露给外部进行自定义
     */
    private Comparator<E> comparator;

    public BinarySearchTree2() {
        this(null);
    }

    public BinarySearchTree2(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        // 1. 添加第一个节点的时候
        if (root == null) {
            root = new Node<>(null, element);
            size++;
            return;
        }
        // 2. 非第一个节点，找到需要添加该元素的父节点
        Node<E> node = root;
        Node<E> parent = null;
        int cmp = 0;
        while (node != null) {
            parent = node;
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                node.element = element;
                return;
            }
        }
        // 3. 增加节点到树上
        Node<E> newNode = new Node<>(parent, element);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

    /**
     * 删除节点
     *
     * @param element 当前元素
     */
    @Override
    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if (node == null) return;
        size--;
        // 度为2的情况，需找到前驱或者后继节点
        if (node.hasTwoChildren()) {
            // 找到后继节点
            Node<E> successor = successor(node);
            node.element = successor.element;
            node = successor;
        }
        // 叶子节点
        if (node.isLeaf()) {
            if (node.parent == null) {
                root = null;
            } else if (node.parent.left == node) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        } else {
            Node<E> replaceNode = node.left != null ? node.left : node.right;
            // 子节点,度为1的节点
            replaceNode.parent = node.parent;
            if (node.parent == null) {
                root = replaceNode;
            } else if (node.left != null) {
                node.parent.left = replaceNode;
            } else {
                node.parent.right = replaceNode;
            }
        }
    }

    private Node<E> node(E element) {
        Node<E> node = root;
        while (node != null) {
            int cmp = compare(element, node.element);
            if (cmp == 0) return node;
            if (cmp > 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    /**
     * 比较两各元素的大小关系，
     * 当e1大于e2时结果大于0
     * 当e1等于e2时结果等于0
     * 当e1小于e2时结果小于0
     *
     * @param e1 元素1
     * @param e2 元素2
     */
    @SuppressWarnings("unchecked")
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }

    @Override
    public boolean contains(E element) {
        return node(element) != null;
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }


    /**
     * 找到后继节点（在大于要删除节点中最小的一个）node.right.left.left.left....
     *
     * @param node 找到当前节点的后继节点
     * @return 后继节点
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) return null;
        // 后继节点在右节点的左子树当中（right.left.left.left....）
        Node<E> s = node.right;
        if (s != null) {
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }
        // 从父节点、祖父节点中寻找后继节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }


    /**
     * 找到前驱节点（在大于要删除节点中最小的一个）node.left.right.right.right....
     *
     * @param node 找到当前节点的前驱节点
     * @return 前驱节点
     */
    private Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        // 后继节点在左节点的右子树当中（left.right.right.right....）
        Node<E> s = node.left;
        if (s != null) {
            while (s.right != null) {
                s = s.right;
            }
            return s;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        return node.parent;
    }


    /**
     * 前序遍历
     */
    public void preorderTraversal() {
        preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node) {
        if (node == null) return;
        System.out.print(node.element + ",");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    private void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.print(node.element + ",");
        inorderTraversal(node.right);
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.element + ",");
    }

    /**
     * 层序遍历 可使用队列来辅助遍历，为何使用队列?
     * 我的理解是层序遍历就是从左到右，顺序遍历 ==> 先进先出
     */
    public void levelOrderTraversal() {
        if (root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.print(node.element + ",");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("添加元素不能为空");
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    @SuppressWarnings("unchecked")
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    @SuppressWarnings("unchecked")
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    @SuppressWarnings("unchecked")
    public Object string(Object node) {
        return ((Node<E>) node).element;
    }

    /**
     * 节点信息
     *
     * @param <E> 泛型E
     */
    private static class Node<E> {
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        E element;

        public Node(Node<E> parent, E element) {
            this.parent = parent;
            this.element = element;
        }

        /**
         * 是否是叶子节点
         *
         * @return true/false
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 是否有两个子节点,若没用两个子节点，则为叶子节点/1个子节点
         *
         * @return true/false
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }
}
